package com.data_structure_algorithm.algorithm;

/**
 * @Authror PABLO
 * @Date 2022/4/5 23:03
 * @Desc 背包问题 含动态规划
 */
public class Bag {

    public static void main(String[] args) {

        //重量
        int[] m = {3, 2, 4, 7, 3, 1, 7};
        //价值
        int[] v = {5, 6, 3, 19, 12, 4, 2};
        //剩余容量（最大容量）
        int bag = 15;

        int i = maxValue1(m, v, bag);
        int i2 = maxValue2(m, v, bag);
        int i3 = maxValue3(m, v, bag);
        System.out.println(i);
        System.out.println(i2);
        System.out.println(i3);
    }

    /**
     * @Description:动态规划版本
     * @Author: PABLO
     * @Date: 2022/4/5 23:04
     * @Params: [m 重量, v 价值, bag 剩余容量]
     * @Return: int 容量内的 最大价值
     **/
    public static int maxValue3(int[] m, int[] v, int bag) {
        int length = m.length;
        int[][] cache = new int[length + 1][bag + 1];//对可变参数设置 缓存

        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {
                if (i == length) {
                    cache[i][j] = 1;
                } else {
                    //有货，index位置 并且bag还有空间
                    //选择1 不要当前的货
                    int p1 = cache[i + 1][j];
                    int p2 = 0;
                    //bag - m[index] 背包减去当前index的容量，即剩余容量
                    //index + 1 不论要不要当前的货，都要进行下一个货物，即下一次调用
                    //process 返回的是最大价值价值
                    int process = j - m[i] < 0 ? -1 : cache[i + 1][j - m[i]];//增加货导致容量小了
                    if (process != -1) {
                        //选择1 要当前的货v[index]保留当前货的价值，  即 该货的价值 +
                        p2 = v[i] + process;
                    }
                    cache[i][j] = Math.max(p1, p2);
                }
            }
        }

        /*
        *
        *
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {
                int p1 = cache[i + 1][j];
                int p2 = 0;
                //bag - m[index] 背包减去当前index的容量，即剩余容量
                //index + 1 不论要不要当前的货，都要进行下一个货物，即下一次调用
                //process 返回的是最大价值价值
                int process = j - m[i] < 0 ? -1 : cache[i + 1][j - m[i]];//增加货导致容量小了
                if (process != -1) {
                    p2 = v[i] + process;
                }

                cache[i][j] = Math.max(p1, p2);
            }
        }
        *  */


        return cache[0][bag];
    }

    /**
     * @Description: 轮到index对应的货物时，bag剩余的容量，而后判断是否留下，返回最大价值  暴力递归版本
     * @Author: PABLO
     * @Date: 2022/4/5 23:05
     * @Params: [m, v, index 具体货物下标, bag 剩余容量]
     * @Return: int 最大价值
     **/
    private static int process(int[] m, int[] v, int index, int bag) {


        int result = 0;
        //背包满了，也有可能是上游调用的时候，在上游背包容量够，但是加上一个货的时候，刚搞到这里超了，那么上游会出问题
        if (bag < 0) {
            result = -1;
        } else if (index == m.length) { //没货了
            result = 0;
        } else {
            //有货，index位置 并且bag还有空间
            //选择1 不要当前的货
            int p1 = process(m, v, index + 1, bag);
            int p2 = 0;
            //bag - m[index] 背包减去当前index的容量，即剩余容量
            //index + 1 不论要不要当前的货，都要进行下一个货物，即下一次调用
            //process 返回的是最大价值价值
            int process = process(m, v, index + 1, bag - m[index]);//增加货导致容量小了
            if (process != -1) {
                //选择1 要当前的货v[index]保留当前货的价值，  即 该货的价值 +
                p2 = v[index] + process;
            }
            result = Math.max(p1, p2);
        }


        return result;


    }

    /**
     * @Description:动态规划版本
     * @Author: PABLO
     * @Date: 2022/4/5 23:04
     * @Params: [m 重量, v 价值, bag 剩余容量]
     * @Return: int 容量内的 最大价值
     **/
    public static int maxValue2(int[] m, int[] v, int bag) {
        int length = m.length;
        int[][] cache = new int[length + 1][bag + 1];//对可变参数设置 缓存

        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {
                int p1 = cache[i + 1][j];
                int p2 = 0;
                //bag - m[index] 背包减去当前index的容量，即剩余容量
                //index + 1 不论要不要当前的货，都要进行下一个货物，即下一次调用
                //process 返回的是最大价值价值
                int process = j - m[i] < 0 ? -1 : cache[i + 1][j - m[i]];//增加货导致容量小了
                if (process != -1) {
                    p2 = v[i] + process;
                }

                cache[i][j] = Math.max(p1, p2);
            }
        }

        for (int[] item : cache
        ) {
            for (int ele : item
            ) {
                System.out.print(ele + "  ");
            }
            System.out.println();
        }

        return cache[0][bag];
    }


    public static int maxValue1(int[] m, int[] v, int bag) {
        return process(m, v, 0, bag);
    }


}
